package com.itheima.leetcode.od.b.stack;

/**
 * (C卷,200分)- 符号运算（Java & JS & Python & C）
 * <p>
 * 题目描述
 * <p>
 * 给定一个表达式，求其分数计算结果。
 * <p>
 * 表达式的限制如下：
 * <p>
 * 所有的输入数字皆为正整数（包括0）
 * <p>
 * 仅支持四则运算（+-* /）和括号
 * <p>
 * 结果为整数或分数，分数必须化为最简格式（比如6，3/4，7/8，90/7）
 * <p>
 * 除数可能为0，如果遇到这种情况，直接输出"ERROR"
 * <p>
 * 输入和最终计算结果中的数字都不会超出整型范围
 * <p>
 * 用例输入一定合法，不会出现括号匹配的情况
 * <p>
 * 输入描述
 * <p>
 * 字符串格式的表达式，仅支持+-* /，数字可能超过两位，可能带有空格，没有负数
 * <p>
 * 长度小于200个字符
 * <p>
 * 输出描述
 * <p>
 * 表达式结果，以最简格式表达
 * <p>
 * 如果结果为整数，那么直接输出整数
 * <p>
 * 如果结果为负数，那么分子分母不可再约分，可以为假分数，不可表达为带分数
 * <p>
 * 结果可能是负数，符号放在前面
 * <p>
 * 用例
 * <p>
 * 输入 1+5*7/8
 * <p>
 * 输出 43/8
 * <p>
 * 说明 无
 * <p>
 * 输入 1/(0-5)
 * <p>
 * 输出-1/5
 * <p>
 * 说明 符号需要提到最前面
 * <p>
 * 输入 1*(3*4/(8-(7+0)))
 * <p>
 * 输出 12
 * <p>
 * 说明 注意括号可以多重嵌套
 */
public class ExpressionCalculator {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);
        s = sc.nextLine().replaceAll(" ", "");  // 读取输入并去除所有空格*/

        s = "1 + 5 * 7 / 8".replaceAll(" ", "");  // 读取输入并去除所有空格
        i = 0;  // 初始化解析位置
        try {
            System.out.println(format(expr()));  // 解析表达式并格式化输出
        } catch (ArithmeticException e) {
            System.out.println("ERROR");  // 捕获除零等算术错误
        }
    }

    static String s;  // 存储去除空格后的表达式字符串
    static int i;     // 当前解析位置的索引

    /**
     * 求两个数的最大公约数（欧几里得算法）
     *
     * @param x 第一个数
     * @param y 第二个数
     * @return 最大公约数
     */
    public static long gcd(long x, long y) {
        return y == 0 ? x : gcd(y, x % y);
    }

    /**
     * 将分数化简为最简形式
     *
     * @param a 分子
     * @param b 分母
     * @return 长度为2的数组，[0]为分子，[1]为分母
     * @throws ArithmeticException 当分母为0时抛出错误
     */
    public static long[] reduce(long a, long b) {
        if (b == 0){
            throw new ArithmeticException("ERROR");  // 分母不能为0
        }
        if (b < 0) {
            a = -a;
            b = -b;
        }  // 将负号统一移到分子上
        long g = gcd(Math.abs(a), b);   // 求分子分母的最大公约数
        return new long[]{a / g, b / g}; // 约分后返回最简分数
    }

    /**
     * 分数加法运算
     *
     * @param f1 第一个分数 [分子, 分母]
     * @param f2 第二个分数 [分子, 分母]
     * @return 相加后的最简分数
     */
    public static long[] add(long[] f1, long[] f2) {
        // 通分相加：a/b + c/d = (a*d + b*c) / (b*d)
        return reduce(f1[0] * f2[1] + f1[1] * f2[0], f1[1] * f2[1]);
    }

    /**
     * 分数减法运算
     *
     * @param f1 被减数 [分子, 分母]
     * @param f2 减数 [分子, 分母]
     * @return 相减后的最简分数
     */
    public static long[] sub(long[] f1, long[] f2) {
        // 通分相减：a/b - c/d = (a*d - b*c) / (b*d)
        return reduce(f1[0] * f2[1] - f1[1] * f2[0], f1[1] * f2[1]);
    }

    /**
     * 分数乘法运算
     *
     * @param f1 第一个分数 [分子, 分母]
     * @param f2 第二个分数 [分子, 分母]
     * @return 相乘后的最简分数
     */
    public static long[] mul(long[] f1, long[] f2) {
        // 分数相乘：a/b * c/d = (a*c) / (b*d)
        return reduce(f1[0] * f2[0], f1[1] * f2[1]);
    }

    /**
     * 分数除法运算
     *
     * @param f1 被除数 [分子, 分母]
     * @param f2 除数 [分子, 分母]
     * @return 相除后的最简分数
     * @throws ArithmeticException 当除数为0时抛出错误
     */
    public static long[] div(long[] f1, long[] f2) {
        if (f2[0] == 0) {
            throw new ArithmeticException("ERROR");  // 不能除以0
        }
        // 分数相除：a/b ÷ c/d = a/b * d/c = (a*d) / (b*c)
        return reduce(f1[0] * f2[1], f1[1] * f2[0]);
    }

    /**
     * 将分数格式化为字符串输出
     *
     * @param f 分数 [分子, 分母]
     * @return 格式化后的字符串（整数直接显示，分数显示为 分子/分母）
     */
    public static String format(long[] f) {
        return f[1] == 1 ? "" + f[0] : f[0] + "/" + f[1];
    }

    /**
     * 解析表达式（处理加法和减法，优先级最低）
     * 文法：expr -> term (('+' | '-') term)*
     *
     * @return 表达式计算结果
     */
    public static long[] expr() {
        long[] f = term();  // 先解析一个项
        // 循环处理所有的加法和减法运算
        while (i < s.length() && (s.charAt(i) == '+' || s.charAt(i) == '-')) {
            char op = s.charAt(i++);  // 获取运算符并移动索引
            f = op == '+' ? add(f, term()) : sub(f, term());  // 根据运算符进行加法或减法
        }
        return f;
    }

    /**
     * 解析项（处理乘法和除法，优先级中等）
     * 文法：term -> factor (('*' | '/') factor)*
     *
     * @return 项的计算结果
     */
    public static long[] term() {
        long[] f = factor();  // 先解析一个因子
        // 循环处理所有的乘法和除法运算
        while (i < s.length() && (s.charAt(i) == '*' || s.charAt(i) == '/')) {
            char op = s.charAt(i++);  // 获取运算符并移动索引
            f = op == '*' ? mul(f, factor()) : div(f, factor());  // 根据运算符进行乘法或除法
        }
        return f;
    }

    /**
     * 解析因子（处理数字和括号，优先级最高）
     * 文法：factor -> '(' expr ')' | number
     *
     * @return 因子的值
     */
    public static long[] factor() {
        if (s.charAt(i) == '(') {  // 如果遇到左括号
            i++;  // 跳过左括号
            long[] f = expr();  // 递归解析括号内的表达式
            i++;  // 跳过右括号
            return f;
        }
        // 解析数字
        long n = 0;
        while (i < s.length() && Character.isDigit(s.charAt(i))) {
            n = n * 10 + s.charAt(i++) - '0';  // 将字符转换为数字并累加
        }
        return new long[]{n, 1};  // 将整数转换为分数形式 n/1
    }
}